#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/8/5 21:33
# @USER    : Shengji He
# @File    : HouseRobber3.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def rob(self, root: TreeNode) -> int:
        """
        The thief has found himself a new place for his thievery again. There is only one entrance to this area,
        called the "root." Besides the root, each house has one and only one parent house. After a tour,
        the smart thief realized that "all houses in this place forms a binary tree". It will automatically
        contact the police if two directly-linked houses were broken into on the same night.

        Determine the maximum amount of money the thief can rob tonight without alerting the police.

        Example 1:
            Input: [3,2,3,null,3,null,1]
                 3
                / \
               2   3
                \   \
                 3   1

            Output: 7

            Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
        Example 2:
            Input: [3,4,5,1,3,null,1]
                 3
                / \
               4   5
              / \   \
             1   3   1

            Output: 9

            Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
        :param root: 
        :return: 
        """
        if not root:
            return 0
        return max(self.dp(root))  # 取root节点偷或不偷的最大值

    def dp(self, root: TreeNode):
        if not root:
            return [0, 0]  # 列表[0]代表当前节点不偷带来的钱，列表[1]代表当前节点偷带来的钱
        lt = self.dp(root.left)  # root的左节点[不偷][偷]带来的钱
        rt = self.dp(root.right)  # root的右节点[不偷][偷]带来的钱
        # root节点不偷，则偷左右儿子节点，取左儿子偷或不偷的最大值和右儿子偷或不偷的最大值；
        # root节点偷，则root节点值+左儿子不偷+右儿子不偷。
        return [max(lt) + max(rt), root.val + lt[0], rt[0]]


if __name__ == '__main__':
    print('done')
